#include<iostream>
using namespace std;
void PartSort1(int* a, int left, int right)//hore
{

    if(left>=right)return ;
    int key =left;
    int i=left,j=right;
    while(i<j)
    {
        while(i<j&&a[j]>=a[key])j--;
        while(i<j&&a[i]<=a[key])i++;
        if(i<j)swap(a[i],a[j]);
    }

    swap(a[key],a[i]);
    PartSort1(a,left,i-1);
    PartSort1(a,j+1,right);

}
int getMedium(int *a,int left,int right)
{
    int medium=(left+right)>>1;
    if(a[left]>a[right])
    {
        if(a[medium]>a[right]&&a[medium]<a[left])
            return medium;
        else if(a[medium]<a[right])
            return right;
        else 
            return left;
    }
    //right>left 
    else {
        if(a[medium]>a[left]&&a[medium]<a[right])
            return medium;
        else if(a[medium]<a[left])
            return left;
        else
            return right;
    }
}
void PartSort2(int* a, int left, int right)//三数
{
    
    if(left>=right)return ;
    int key =getMedium(a,left,right);
    if(a[key]!=a[left])swap(a[key],a[left]);
    int i=left,j=right;
    while(i<j)
    {
        while(i<j&&a[j]>=a[key])j--;
        while(i<j&&a[i]<=a[key])i++;
        if(i<j)swap(a[i],a[j]);
    }

    swap(a[key],a[i]);
    PartSort2(a,left,i-1);
    PartSort2(a,j+1,right);
}
void PartSort3(int* a, int left, int right)//挖坑
{
    if(left>=right)return ;
    int key=getMedium(a,left,right);
    if(key!=left)swap(a[left],a[key]);
    key=left;
    int begin=left,end=right;

    int value=a[begin];

    int hole=begin;

    while(begin<end)
    {
        while(begin<end&&a[end]>=value)end--;
        a[hole]=a[end];
        hole=end;
        while(begin<end&&a[begin]<=value)begin++;
        a[hole]=a[begin];
        hole=begin;
    }
    a[hole]=value;
    PartSort3(a,left,hole-1);
    PartSort3(a,hole+1,right);
}
void PartSort4(int* a, int left, int right)//双指针
{
    if(left>=right)return ;
    int key=getMedium(a,left,right);
    if(key!=left)swap(a[left],a[key]);
    key=left;
    int prev=left,cur=left+1;
    while(cur<=right)
    {
        if(a[cur]<a[key]&&++prev!=cur)
        {
            swap(a[cur],a[prev]);
        }
        ++cur;
    }
    swap(a[prev],a[key]);
    PartSort4(a, left,prev-1);
    PartSort4(a, prev+1,right);
}
int main()
{
    int a[]={9,3,1,2,4,2,2,5};
    int len=(sizeof(a)/sizeof(a[0]));
    PartSort4(a,0,len-1);
    for(int i=0;i<len;i++)
        cout<<a[i]<<" ";
    return 0;
}